package doing.doing_501_1000;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.io.UnsupportedEncodingException;

/**
 * 977. Squares of a Sorted Array  有序数组的平方
 * <p>
 * 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
 * <p>
 * 示例 1：
 * 输入：[-4, -1, 0,  3,  10]
 * 输出：[ 0,  1, 9, 16, 100]
 * <p>
 * 示例 2：
 * 输入：[-7, -3, 2,  3,  11]
 * 输出：[ 4,  9, 9, 49, 121]
 * 提示：
 * 1   <= A.length <= 10000
 * -10000 <=   A[i]   <= 10000
 * <p>
 * A 已按非递减顺序排序。
 *
 * @author wangxiaozhe
 */
@Slf4j
public class SquaresOfASortedArray {

    @SuppressWarnings("all")
    public int[] sortedSquares(int[] A) {
        int[] result = new int[A.length];

        //找出最小元素的下标
        int min = 0;
        for (int i = 0; i < A.length; ++i) {
            if (Math.abs(A[min]) > Math.abs(A[i])) {
                min = i;
            }
        }

        //从最小元素开始往两边遍历
        int h = min >= A.length - 1 ? min - 1 : min;
        int t = h + 1;

        int ind = 0;
        while (h >= 0 && t < A.length) {
            if (Math.abs(A[h]) <= Math.abs(A[t])) {
                result[ind++] = A[h] * A[h--];
            } else {
                result[ind++] = A[t] * A[t++];
            }
        }

        //剩下的数依次加入到结果中即可
        while (h >= 0) {
            result[ind++] = A[h] * A[h--];
        }

        while (t < A.length) {
            result[ind++] = A[t] * A[t++];
        }
        return result;
    }

    @Test
    public void test() throws UnsupportedEncodingException {
        int[] arr = new int[]{-7, -3, 2, 3, 11};
        log.info("result:{}", sortedSquares(arr));
    }
}









































/*
public int[] sortedSquares(int[] A) {
    int[] result = new int[A.length];

    //找出最小元素的下标
    int min = 0;
    for (int i = 0; i < A.length; ++i) {
        if (Math.abs(A[min]) > Math.abs(A[i])) {
            min = i;
        }
    }

    //从最小元素开始往两边遍历
    int h = min >= A.length - 1 ? min - 1 : min;
    int t = h + 1;

    int ind = 0;
    while (h >= 0 && t < A.length) {
        if (Math.abs(A[h]) <= Math.abs(A[t])) {
            result[ind++] = A[h] * A[h--];
        } else {
            result[ind++] = A[t] * A[t++];
        }
    }

    //剩下的数依次加入到结果中即可
    while (h >= 0) {
        result[ind++] = A[h] * A[h--];
    }

    while (t < A.length) {
        result[ind++] = A[t] * A[t++];
    }
    return result;
}
*/
